#include"sort.h"
#include"Stack.h"
// 排序实现的接口
// 插入排序，时间复杂度为O(N*N),空间复杂度为O(1)
void InsertSort(int* a, int n)
{
	assert(a);
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];//[0,end]有序，将end+1的元素往[0,end]里面插入
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;	
			}
			else
			{
				break;//将在序列中的插入与序列头的插入合起来考虑
			}
		}
		a[end + 1] = tmp;
	}
}
// 希尔排序 1、先进行预处理（使得数组接近有序） 2、然后进行插入排序
//希尔排序的时间复杂度O(N^1.3-N^2),也有可能其时间复杂度比直接插入排序低
void ShellSort(int* a, int n)
{
	assert(a);
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;//加一保证gap能取到1，取到1则保证了插入排序为绝对有序(直接插入排序)
		for (int i = 0; i < n - gap; i++)//保证每一个gap下的每组数组都能进行插入排序
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > tmp)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end + gap] = tmp;
		}
	}
}
void Swap(int* p1,int* p2)//交换
{
	int tmp = *p2;
	*p2 = *p1;
	*p1 = tmp;
}
//// 选择排序,加强版选择排序，指定两个指针最大和最小，每一次遍历找出最大和最小。
void SelectSort(int* a, int n)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	while (begin <= end)
	{
		int mini, maxi;
		mini = maxi = begin;//找出的是最大数和最小数的坐标
		//第一遍遍历找出最小的数
		for (int i = begin + 1; i <= end; i++)
		{
			if (a[mini] > a[i])
			{
				mini = i;
			}
			if (a[maxi] < a[i])
			{
				maxi = i;
			}
		}
		Swap(&a[begin], &a[mini]);
		if (begin == maxi)//这里防止begin和maxi重叠的情况
		{
			maxi = mini;
		}
		Swap(&a[maxi], &a[end]);
		end--;
		begin++;
	}
}
// 堆排序
void AdjustDwon(int* a, int n, int root)//向下调整算法
{
	int parent = root;
	int child = 2 * parent + 1;
	while (child < n)
	{
		if (child+1<n&&a[child] < a[child + 1])
		{
			child++;
		}
		if (a[parent] < a[child])
		{
			Swap(&a[parent], &a[child]);
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}
void HeapSort(int* a, int n)//排序
{
	//建大堆
	//给出一个数组，从最后一个元素开始不断用向下调整算法建堆
	int i = 0;
	int end = n - 1;
	for (i = (n - 1 - 1) / 2; i >=0;i--)//建堆
	{
		AdjustDwon(a,n,i);
	}
	//排序
	while (end > 0)
	{
		Swap(&a[0], &a[end]);//因为是大堆，所以每次将堆顶的元素与队尾元素进行交换，再进行向下调整算法。
		AdjustDwon(a, end, 0);
		end--;
	}
}
//// 冒泡排序复杂度O(N^2)
void BubbleSort(int* a, int n)
{
	int i = 0;
	int exchange = 0;
	int end = n;
	while(end>0)
	{
		for (i = 1; i < end; i++)
		{
			if (a[i-1] > a[i])
			{
				Swap(&(a[i-1]), &a[i]);
				exchange = 1;
			}
		}
		if (exchange == 0)//如果第一遍冒泡循环没有发生交换，则直接跳出
		{
			break;
		}
		end--;//每一个循环冒泡就会把最大的数放在数组最后，然后再对剩余数组进行冒泡
	}
}
//// 快速排序递归实现
//// 快速排序hoare版本
//快排优化
int MiddleIndex(int* a, int begin, int end)//快速排序时，如果key选择最大或者最小其效率会大大降低，下用三位取中来保证选择的key不是最大或最小
{
	int mid = (begin + end) / 2;
	if (a[begin>a[mid]])
	{
		if (a[mid] > a[end])
			return mid;
		else if (a[end] > a[begin])
			return begin;
		else
			return end;
	}
	else
	{
		if (a[end] > a[mid])
			return mid;
		else if (a[end] < begin)
			return begin;
		else
			return end;
	}
}
//有了三数取中，最坏的情况不会出现O（N^2），所以综合而言快排的复杂度为O（NlogN）
int PartSort1(int* a, int begin, int end)//左右指针法
//单趟：1、把比key大的放在右边，比key小的放在左边  2、key的位置就是其排序后的位置不用动
{
	int mid = MiddleIndex(a, begin, end);//获取到三位中数
	Swap(&a[mid], &a[end]);//将中数和最后一个数进行调换，满足后面的取最后一个数作为key
	int key = a[end];//这里注意有个规则，如果选择最右边的数作为key，则一定要让左边的begin先走，这样能保证他们相遇的位置是一个比key大的值，这样和key交换之后才能保证key左边全比其小，右边全比其大
	//反之则反过来
	int keyindex = end;//记录key的位置，将来要交换
	while (begin < end)
	{
		while (begin<end&&a[begin] <= key)
		{
			begin++;
		}
		while (begin<end&&a[end] >= key)
		{
			end--;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[keyindex]);//将key换过来
	return begin;//返回划分点
}

// 快速排序挖坑法
int PartSort2(int* a, int begin, int end)
{
	int mid = MiddleIndex(a, begin, end);
	Swap(&a[mid], &a[end]);
	int key = a[end];//选择最后一个作为坑，且记录坑
	while (begin < end)
	{
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[end] = a[begin];//从begin开始找，找到第一个比key大的数放在之前的坑里，现在位置重新变成坑
		while (begin < end && a[end]>=key)
		{
			end--;
		}
		a[begin] = a[end];//接着从end找，找到第一个比key小的数放在前坑中
	}
	a[begin] = key;//最后begin和end相遇处就是一个坑，把key放此坑中。
	return begin;
}
//// 快速排序前后指针法(抽象)
int PartSort3(int* a, int begin, int end)
{
	int key = a[end];
	int prev = begin-1;
	int cru = begin;
	while (cru<end)
	{
		if(a[cru] < key&&++prev!=cru)
			Swap(&a[prev], &a[cru]);
		cru++;
	}
	Swap(&a[++prev], &a[end]);
	return prev;
}
void QuickSort(int* a, int left, int right)
{
	assert(a);
	if (left > right)
		return;
	if(right-left+1>10)//快排的优化
	{
		int div = PartSort3(a, left, right);
		QuickSort(a, left, div - 1);//递归
		QuickSort(a, div + 1, right);
	}
	else//当区间小于等于10的时候不再用快排的递归，用插入排序减少整体的递归次数
	{
		InsertSort(a + left, right - left + 1);
	}
}
//void QuickSort(int* a, int left, int right);
//// 快速排序 非递归实现时间复杂度O（NlogN）空间复杂度O（logN）
//递归改非递归法1、改循环（如斐波那契额列求解），一些简单递归才能改循环2、利用栈模拟存储数据非递归
//改非递归意义1、提高效率（递归建立栈帧还是有消耗的，但对于现代计算机，这个消耗微乎其微可以忽略不计）
//2、递归最大的缺点是，如果递归建立的栈帧太深有可能会导致栈溢出，因为系统栈空间一般不大在M左右
//但是栈存储在堆上，堆是以G级别的容量。
//void QuickSortNonR(int* a, int left, int right)
//{
//	Stack* st;
//	StackInit(&st);
//
//	StackPush(&st, right);
//	StackPush(&st, left);
//
//	while (!StackEmpty(&st))
//	{
//		int begin = StackTop(&st);
//		StackPop(&st);
//		int end = StackTop(&st);
//		StackPop(&st);
//
//		int div = PartSort3(a, begin, end);
//		if (div + 1 < end)
//		{
//			StackPush(&st, end);
//			StackPush(&st, div + 1);
//
//		}
//		if (div - 1 > begin)
//		{
//			StackPush(&st, div - 1);
//			StackPush(&st, begin);
//		}
//
//	}
//	StackDestroy(&st);
//}
// 归并排序递归实现，之前的排序可以归类为内排序，下面的排序可以归并为外排序，即对文件数据进行排序
//递归思想方法：主要利用合并有序数组的方法，利用递归思想将整个数组不断分成小部分，对小部分不断进行有序数组合并
//只需要开辟一个数组空间，合并之后把数组再复制上去。时间复杂度O（NlogN）空间复杂度O（N）
void MergerArr(int *a,int begin1,int end1,int begin2,int end2,int *tmp)
{
	int left = begin1;
	int right = end2;
	int index = begin1;//记录合并数组的下标，方便后面往回拷贝
	while (begin1 <= end1 && begin2 <= end2)//两个数组其中一个结束那就结束
	{
		if (a[begin1] < a[begin2])
			tmp[index++] = a[begin1++];
		else
			tmp[index++] = a[begin2++];
	}
	//把长的数组的后面接到tmp面
	while (begin1 <= end1)
	{
		tmp[index++] = a[begin1++];
	}
	while (begin2 <= end2)
	{
		tmp[index++] = a[begin2++];
	}
	//把归并好的数组再拷贝回原来的数组
	for (int i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}
void _MergeSort(int* a, int left, int right, int* tmp)
{
	if (left >= right)//递归停止条件
		return;
	int mid = (left + right) / 2;//取中间的位置
	_MergeSort(a, left, mid, tmp);//前半段递归
	_MergeSort(a, mid + 1, right, tmp);//后半段递归
	//下面进行有序数组的合并
	//int begin1 = left;
	//int end1 = mid;
	//int begin2 = mid + 1;
	//int end2 = right;
	//int index = begin1;//记录合并数组的下标，方便后面往回拷贝
	//while (begin1 <= end1 && begin2 <= end2)//两个数组其中一个结束那就结束
	//{
	//	if (a[begin1] < a[begin2])
	//		tmp[index++] = a[begin1++];
	//	else
	//		tmp[index++] = a[begin2++];
	//}
	////把长的数组的后面接到tmp面
	//while (begin1 <= end1)
	//{
	//	tmp[index++] = a[begin1++];
	//}
	//while (begin2 <= end2)
	//{
	//	tmp[index++] = a[begin2++];
	//}
	////把归并好的数组再拷贝回原来的数组
	//for (int i = left; i <= right; i++)
	//{
	//	a[i] = tmp[i];
	//}
	MergerArr(a, left, mid, mid + 1, right, tmp);

}
void MergeSort(int* a, int n)
{
	assert(a);
	//开辟数组
	int* tmp = malloc(sizeof(int) * n);
	_MergeSort(a, 0, n-1,tmp);//子函数
	free(tmp);
}
// 归并排序非递归实现
void MergeSortNonR(int* a, int n)
{
	assert(a);
	int* tmp = malloc(sizeof(int) * n);
	int gap = 1;
	while(gap<n)
	{
		for (int i = 0; i < n; i += 2 * gap)//第一次合并
		{
			int begin1 = i;
			int end1 = i + gap - 1;
			int begin2=i+gap;
			int end2=i+2*gap-1;
			//合并时只有第一组有数据
			if (begin2 >= n)
			{
				break;
			}
			//合并时第二组只有部分数据，对第二组的边界进行修正
			if (end2 >= n)
			{
				end2 = n - 1;
			}
			MergerArr(a, begin1,end1,begin2,end2, tmp);
		}
		gap *= 2;
	}
	free(tmp);
}
// 计数排序,记录每个数字出现多少次然后进行排序
void CountSort(int* a, int n)
{
	assert(a);
	//需要相对位置先求数组中的最大值和最小值
	int min = a[0];
	int max = a[0];
	for (int i = 0; i < n; i++)
	{
		if (a[i] > a[0])
			max = a[i];
		if (a[i] < a[0])
			min = a[i];
	}
	int range = max - min + 1;//记录数组中一共有多少种数字
	int* CountArr = malloc(sizeof(int) * range);//开辟空间存放这些数字的个数
	memset(CountArr, 0, sizeof(int)*range);//初始化数组全为0
	//记录数字的个数
	for (int j = 0; j < n; j++)
	{
		CountArr[a[j]-min]++;//求相对位置
	}

	//排序
	int index = 0;
	for (int j = 0; j < range; j++)
	{
		while (CountArr[j]--)
		{
			a[index++] = min + j;
		}
	}
	free(CountArr);
}
//// 测试排序的性能对比
//void TestOP()
//{
//	//srand(time(0));//随机数
//	//const int N = 100000;
//	//int* a1 = (int*)malloc(sizeof(int) * N);//创建数组10000个大小
//	//int* a2 = (int*)malloc(sizeof(int) * N);
//	/*int* a3 = (int*)malloc(sizeof(int) * N);
//	int* a4 = (int*)malloc(sizeof(int) * N);
//	int* a5 = (int*)malloc(sizeof(int) * N);
//	int* a6 = (int*)malloc(sizeof(int) * N);*/
//	/*for (int i = 0; i < N; ++i)
//	{
//		a1[i] = rand();
//		a2[i] = a1[i];*/
//		/*a3[i] = a1[i];
//		a4[i] = a1[i];
//		a5[i] = a1[i];
//		a6[i] = a1[i];*/
//	}
//	//int begin1 = clock();//记录运行开始时间
//	//InsertSort(a1, N);
//	//int end1 = clock();//记录运行结束时间
//	//int begin2 = clock();
//	//ShellSort(a2, N);
//	//int end2 = clock();
//	/*int begin3 = clock();
//	SelectSort(a3, N);
//	int end3 = clock();
//	int begin4 = clock();
//	HeapSort(a4, N);
//	int end4 = clock();
//	int begin5 = clock();
//	QuickSort(a5, 0, N - 1);
//	int end5 = clock();
//	int begin6 = clock();
//	MergeSort(a6, N);
//	int end6 = clock();*/
//	//printf("InsertSort:%d\n", end1 - begin1);
//	//printf("ShellSort:%d\n", end2 - begin2);
//	/*printf("SelectSort:%d\n", end3 - begin3);
//	printf("HeapSort:%d\n", end4 - begin4);
//	printf("QuickSort:%d\n", end5 - begin5);
//	//printf("MergeSort:%d\n", end6 - begin6);*/
//	//free(a1);
//	//free(a2);
//	/*free(a3);
//	free(a4);
//	free(a5);
//	free(a6); */
//}